NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part1/5394

Text File | 1996-08-05 | 20.2 KB | 482 lines

Path: news1.halcyon.com!coho!riston
From: [e-mail] (Michael D. Riston)
Newsgroups: comp.lang.c++
Subject: SUMMARY: A Good UNDO Design
Date: 4 Feb 1996 08:55:36 GMT
Organization: Northwest Nexus Inc.
Message-ID: <4f1sa8$[e-mail]>
NNTP-Posting-Host: coho.halcyon.com


Hello Designers!

This summary contains the responses received for a question posted on the
net asking for any ideas on an elegant object oriented design for
implementing Undo/Redo.  Hope this helps.

Mike Riston
E-Mail - [e-mail]
Web    - http://www.halcyon.com/riston

The original question
---------------------

   I have been charged with designing an undo mechanism for a large
   graphical Windows (32bit) application.  This application is the classic
   'draw a shape' program (box, circle, line, OLE object, or whatever).
   I would like to know if anybody has any elegant designs for handling
   undo operations.  I am working with Visual C++ 4.0 and MFC for the
   implementation.  I am well versed in C++.


My own comments
---------------

   Thank you to all who submitted answers to this question!  The most
   common answer was the 'Command' pattern found in the 'Design Patterns'
   book, by Gamma, Helm, Johnson, and Vlissides.  By far the benefits of
   using this design make this a classic answer for the Undo/Redo design.
   This is the method that our design will take.  Many people pointed to
   Jim Beveride's Undo/Redo article in the Feb 1996 issue of Dr. Dobbs as
   an Undo/Redo example.  His design basically implements the 'Command'
   pattern, with a fancy Undo/Redo command list manager class that he
   calls CForeman.  The summary reads.

      "Implementing Multilevel UNDO/REDO by Jim Beveridge. The Undo/Redo
      mechanism Jim presents here is based on a history length limited
      only by available memory.  Because it is implemented in Visual C++
      and MFC, this machanism can easily be added to your applications."

   Below is a selected list of answers received from netland.  Most seem
   to use the 'Command' pattern with different twists and turns.


   ----------------------------------------------------------------------
   [e-mail] (Enno Sandner) Writes
   ----------------------------------------------------------------------

   A neat solution to this problem is the 'Command' pattern as described in
   the 'Design Patterns' book. The main idea is to encapsulate the necessary
   steps to perform a specific behavior in objects that conform to an unique
   interface. The interface provides the services 'Do' and 'Undo'. It is
   represented by the abstract 'Command' class:

        class Command {
          public:
            virtual ~Command() {}
            virtual void Do()=0;
                    virtual void Undo()=0;
                };

   Every operation that affects the graphical appearence must have its counter-
   part that reverses the operation and both operations should be encapsulated
   in a subclass of 'Command'. For example a circle may look like:

        class CircleCommand : public Command {
          public:
           CircleCommand(Painter& p,int x,int y,int r) :
            p_(p), x_(x), y_(y), r_(r) {}
           void Do() { p_.DrawCircle(x_,y_,r_); }
           void Undo() { p_.RemoveCircle(x_,y_,r_); }
        };

   Moving a graphical object is another example for an operation that should
   be wrapped.  Finally you need a manager to register the commands. The
   manager maintains a finite command history and allows you to move backwards
   and forwards in the history. The former results in undoing the latter in
   executing the command.

    Enno



   --------------------------------------
   [e-mail] (Richard Wells) Writes
   --------------------------------------

   Here's a technique I've seen used:

   class Command
   {
       virtual void Do();
       virtual void Undo();
       virtual void Redo();
       virtual void Commit();
   };

   Each individual command is represented by a class derived from Command,
   with implementations for these 4 functions.  The past n commands (where
   n is the size of the undo buffer) are kept in a queue of sorts; it isn't
   quite a strict queue, as we'll see, but calling it a queue will suffice
   for now.

   The Do() function is called when the command is first issued.  This
   does everything necessary to make it appear to the user that the command
   has been carried out, except that it does not permanently affect the
   underlying data.  It also must keep around whatever data is necessary
   to undo the command.

   The Undo() function is called when the command is undone.  It must make
   it appear to the user that the command has been undone.  Like Do(), it
   makes no permanent changes to the underlying data.

   The Redo() function is called when the command is being redone.  It is
   generally very similar to Do(); it does whatever it takes to make it
   appear to the user that the command has been redone, without permanently
   changing the underlying data.

   Finally, Commit() is called to make the necessary changes to the underlying
   data to make an undo impossible.

   Now for the undo buffer: this is actually a queue (sort of) of command
   instances.  New commands are added to the head, and old commands are
   removed as necessary from the tail.  However, this is not a strict queue,
   because we also need to keep a pointer to the middle of the queue; for
   reasons that will become obvious, we'll call this the stack pointer.

   When the user selects "undo", the Undo() function of the command pointed
   to by the stack pointer is called, and the stack pointer is modified to
   point to the previous Command.  Note that the Command object whose Undo()
   function was called is NOT removed from the queue.

   When the user selects "redo", the stack pointer is modified to point to
   the next Command object, and its Redo() function is called.

   To add a new command to the queue, all Command objects between the stack
   pointer and the head of the queue (if any) are removed, the new Command
   object is added at the head of the queue, and its Do() function is called.
   The stack pointer is modified to point to this new object, as it will be
   the first to be undone if the user issues an "undo" command.  If there is
   a limit to the size of the undo buffer (i.e., the number of Command objects
   in the queue), the Commit function for the Command at the tail of the queue
   is called, and that Command object is removed.

   Before a "save" command, all Command objects (if any) between the stack
   pointer and the head of the queue are removed, and all remaining objects
   in the queue have their Commit() functions called (starting at the tail
   of the queue); they are then also removed.  (Unless you want to be able to
   Undo() saved operations.  Be warned: there lies madness.)

   For example, consider an AddCircle command.  The Do() function would
   draw the circle and store its center and radius.  The Undo() function
   would remove the circle from the screen.  The Redo() function would
   draw the circle again.  The Commit() function would add a circle object
   to the database.

   Of course, TANSTAAFL.  A redraw would also need to be able to cruise
   through the undo buffer to redraw all those objects between the tail
   of the queue and the stack pointer; this may or may not be the same
   as the Redo() function, depending on circumstances.  (If you use a
   model where your display list is separate from the database, this may
   not be a concern, but then the Do(), Undo(), and Redo() functions must
   do the right thing with the display list.)  There are probably other
   real-world considerations I'm glossing over, but I think this scheme
   is generally workable.

   Note that if all works according to plan, the Undo() function may
   assume that the world is in the same state as it was after the command
   was first issued, and the Redo() function may assume it is in the
   same state as before the command was first issued.  So, for example,
   the Add Circle command need not concern itself with the possibility
   that a subsequent Move Object command moved the circle; if the user
   has issued "undo" commands to the point where the Add Circle is being
   undone, it can assume that the Move Object has also been undone, and
   the circle is exactly where it was after the Add Circle command was
   originally executed.

   Now for the final caveat: I've never had a client who thought that
   undo/redo was important enough to pay for the time it takes to
   implement this scheme.  So if you use it, let me know how it works
   out (:-).

   Opinions expressed herein are my own and may not represent those of 3M.


   ------------------------------------------
   Seth Goldstein <[e-mail]> Writes
   ------------------------------------------

   One classic design for unlimited undo/redo is to encapsulate
   each user-initiated command in an object, along with enough
   information to undo the command or redo it if necessary
   (subclass the commands to add this information, and any
   additional information such as some text describes the
   operation).  Each command object supports an Execute and an
   Unexecute operation.

   The undo manager maintains a series of command objects along
   with an indicator for "the present".

   Undo causes the undo manager to call Unexecute on the command
   prior to "the present", and move the "present indicator" one
   notch back.

   Redo causes the undo manager to call Execute on the command just
   after "the present", and move the "present indicator" one notch
   forward.

   There are details to work out regarding commands which are
   expensive or impossible to undo, commands which have no effect,
   and what to do with the "future" of the command stream when the
   user issues an undo followed by a new command.

   Hope this is a start,
   Seth

   P.S.: See Gamma, Helm, Johnson, Vlissides, _Design_Patterns_






   --------------------
   [e-mail] Writes
   --------------------

   I have no source code, but if you want to see how it should work from a
   users perspective check out the Describe wordprocessor (it's about $50).
   Instead of the usual Undo/Redo menu options, there is a dialog box with
   a slider bar which allows you to slide back and forth through
   the complete history of operations.  Two ways I can see of doing this
   is make every operation reversible which is more complicated, or only
   keep a copy of the original document and apply the users instructions
   to it up to the current undo/redo level, which would be simple but slow.
   Either way you need some sort of stack of instructions, perhaps using
   an internal macro or symbolic language.

   Dave


   ------------------------------------------------------------------------
   [e-mail] (Jim Beveride: Author of Dr. Dobbs article) Writes
   ------------------------------------------------------------------------

   > >
   > > I wrote an article that is in this month's Dr. Dobbs Journal
   > > about implementing multilevel Undo/Redo in C++ (and MFC).
   > > It essentially uses the scheme mentioned in a previous post.
   > >
   > > See the February "Dr.Dobbs Journal", which is on shelves now
   >
   > I picked up a copy today and read the article.  It was very good.
   > It very much follows the Command pattern found in the
   > "Design Patterns" book.
   >
   > One question, however.   Your undo implementation does not span
   > over multiple documents (i.e. it has a separate undo list for each
   > document).  I have seen other applications (namely Visio) implement
   > UNDO across documents.   For example,  a user puts down a circle in
   > one document, then puts down a square in another, and then undoes
   > both operations and it undoes both documents automatically.   Your
   > spiral program (which I download) did not do this.
   >
   > Do you have any further ideas on how to implement this?  You
   > mentioned in your article that one would need to implement a
   > GetFocusTask, but yet you would not want the user to see this in the
   > undo list.
   >
   > Thanks for your input on this topic.
   >
   > ......Mike....:)

   Mike,

   I tried Visio, and it does indeed do what you describe.  I would argue
   that this approach is wrong because it is application-centric instead
   of document-centric.  In other words, if I want to work on several
   documents that are completely unrelated, I cannot randomly switch
   between documents (for example, while one is repaginating or printing)
   and then go back to the "context" of my original document.  It is also
   confusing because multiple instances will work differently than a single
   instance with several MDI windows.  And what happens if the user closes
   a document that is in the undo history... Do you throw away changes
   that referred to that document?  What if it was a drag-and-drop
   operation BETWEEN the two documents?  What if the original view
   on the document is gone, but there is another view that could
   be switched back to instead?

   Anyway, if you still want to do it, you can implement a global
   undo history by putting the undo history at the mainframe level
   instead of at the document level.  Each undo task would keep
   a pointer to the document and view it referred (although there
   are problems with this, see above)  Undo is then processed by
   the mainframe, which checks the active view (and document)
   and switches it if necessary.


   Best of luck,
   Jim Beveridge




   --------------------------------------------
   [e-mail] (Carter Maslan) Writes
   --------------------------------------------

   Has anyone tried implementing Undo using OLE's Compound Files
   TRANSACTED mode with the revert command?  Inside OLE 2
   inferred that it might be an easy way to support Undo.

   ------------------------------------------------------
   From: [e-mail] (John B. Williston) Writes
   ------------------------------------------------------

   >Has anyone tried implementing Undo using OLE's Compound Files
   >TRANSACTED mode with the revert command?  Inside OLE 2
   >inferred that it might be an easy way to support Undo.

   You *really* don't want to do that (grin).  Each open OLE storage eats
   a chunk of memory and 2 or 3 open file handles.  Using transacted mode
   just makes it worse.  My personal preference is to package commands as
   objects that have Do/Undo methods.

   John

   (Note.  This thread continues in comp.os.ms-windows.programmer.win32.
    for more information on this see this newsgroup).




   ----------------------------------------------------------------
   [e-mail] (Joseph Cascio, Jr. // Augusta Development) Writes
   ----------------------------------------------------------------

   There are two classic approaches to undo: "inverse command" and
   "checkpoint".  In the "inverse command" approach, whenever you execute
   a command on the drawing, like "move", you save the fact that you did
   a "move", along with its arguments on a list.  To undo, you perform
   the "inverse" operation, which would be a move with the arguments negated,
   or however you find it easy to do.  This works as long as the functions
   don't have a lot of side effects.  A side effect would occur, for example,
   in a directed-graph type of drawing in which objects are "connected" to
   other objects using lines - a schematic or flowchart, for instance.  When
   you move one object, you may indirectly cause movement or changes of many
   other objects in ways that are difficult to capture because there is no
   direct "command" corresponding to that operation.

   In such cases, I prefer the "checkpoint" approach, in which you make a
   copy of each object before you modify it, then go ahead and do whatever
   operation you want, then save a copy after all operations are done.  The
   undo record then consists of a two-part record for each operation
   performed, which has a "before" list of objects, and an "after" list.
   To undo, you remove the existing copy of the object, and restore the
   "before" copy.  To "redo", you remove the existing copy, and restore the
   "after" copy.

   This may cost more in space, but has the benefit that it works no matter
   what operation you perform, and no matter how many objects it touches.
   Also, you don't have to write anything additional when you add new
   functions.  You do have to write an object-clone constructor, and a
   pointer-mapper, for each new object type you add, however.

   This is a pretty condensed explanation, and I'm sure I've raised more
   questions than I've answered, but perhaps I've launched you in some
   direction.  I've implemented a couple of versions of the "checkpoint"
   approach, and found it works pretty well.  Most apps you see today use
   the "inverse" approach, however.  This is simpler for simple applications,
   but is limited in the kind of operations it can capture.

   BTW, my company specialize in the types of applications you describe for a
   living.  Augusta is in the process of delivering the first release of a
   product for building direct-manipulation diagram editors for Visual C++/MFC.

   -JC



   --------------------------------------------------
   [e-mail] (Kevin Cline) Writes
   --------------------------------------------------

   I feel strongly that programs that have an undo feature should allow
   the user to undo multiple actions one at a time, all the way back to
   the beginning of the edit session (i.e. back to an empty workspace or
   back to the point a file was loaded).  With only a single undo it is
   too easy for a user to do two things, find that the second-from-last
   can't be undone, and then the user has to start over from the last
   save.  Disk and memory are cheap, so there is no reason not to buffer
   up lots of previous actions.

   Keep all the previous actions in a list, like this.

   -----------------------------
   | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
   -----------------------------
                 ^

   There are three possible user actions: edit, undo, redo.

   Edit erases all actions to the right of the undo pointer
   adds the new action to the end of the list, and puts the undo
   pointer under the new action.

    -------------------------------
   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
    -------------------------------
                 ^
   Undo undoes the action above the undo pointer and moves the undo pointer
   to the left.

   ----------------------------
   | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
   ----------------------------
             ^
   Redo moves the undo pointer to the right and redoes the action above
   the pointer.

   If you have undo and redo in a menu, then the entries could change
   to show what will be undone or redone.

   GNU Emacs has a different design; instead of redo, it has undo and undo more.
   The edit list records every state change, even those caused by undo.

   Initial state:

   ----------------
   | 1 | 2 | 3 | 4 |
   ----------------

   After undo:

    -------------------------------
   | 1 | 2 | 3 | 4 | 5 (undoing 4) |
    -------------------------------
         ^

   After another undo:

    ------------------------------------------------------
   | 1 | 2 | 3 | 4 |      5      |           6            |
   |   |   |   |   | (undoing 4) | (undoing 5, redoing 4) |
    ------------------------------------------------------
         ^

   After undo more:

    ---------------------------------------------------------
   | 1 | 2 | 3 | 4 |      5      |     6       |     7       |
   |   |   |   |   | (undoing 4) | (redoing 4) | (undoing 4) |
    ---------------------------------------------------------
         ^

   After another undo more:

    -----------------------------------------------------------------------
   | 1 | 2 | 3 | 4 |      5      |     6       |     7       |      8      |
   |   |   |   |   | (undoing 4) | (redoing 4) | (undoing 4) | (undoing 3) |
    -----------------------------------------------------------------------
     ^

   --
   Kevin Cline


--
--------------------------------------------------------------------------
Mike and Hilda Riston    Email  -  [e-mail]
21311 52nd Ave SE    Voice  -  [phone]
Woodinville, WA 98072   Web    -  http://www.halcyon.com/riston